A database is a collection of related records stored in a computer. In the art, this collection of data records is also referred to as an information database. Data records are alternatively referred to as data tuples, or simply tuples. Multiple users may concurrently access these data records. Transactions are run on behalf of database users to access these data records. A transaction may read from the database, write into the database, or do both. Thus, transaction execution yields a set of read and write operations on a set of data records. Transactions typically request access permissions for the data records they read or write. Access permissions are usually implemented via locks. A transaction typically requests access permission on a data record by asking for a corresponding lock. Conflicts in access permissions manifest themselves as lock conflicts. Lock conflicts may arise when multiple transactions try to access the same data record at the same time in incompatible modes.
One of the ways to resolve lock conflicts is to make conflicting transactions wait. For example, the transaction that issued a conflicting lock request on a data record is forced to wait until the transaction that already owns a lock on the same record completes its execution (By completion of a transaction we mean that the transaction either commits or rollbacks). However, in such a scenario, two or more transactions may end up in a deadlock where each transaction waits for the other transaction to complete, thereby preventing either one from making any progress.
Many techniques have been invented for reducing the amount of locks used in transactional systems, such as timestamp ordering, validation, and multi-version schemes. Out of these schemes, multi-version schemes have become commercially successful, and many vendors use these schemes. In a typical multi-version scheme, write operations on a data record create new versions of the record, and read operations select an appropriate version of the record from the available versions for reading. In this type of database systems, multiple versions of a data record may exist simultaneously. Some of these versions may not be used by any currently executing or future transactions. These unused versions are referred to as “garbage”. Hence, these systems need to employ garbage collection mechanisms to reclaim space occupied by the unused versions. Many multi-version database schemes have lazy garbage collection where old versions of data records exist in the database longer than is necessary, and are unbounded in terms of how long garbage may exist in that database.
Concurrent execution of multiple transactions requires that there be some protection of a given transaction from other transactions. This protection that a transaction has from other transactions is called its “isolation”. For example, if a transaction executes a write operation on a data record, then the new data value should not be read by any other transaction until the former transaction is complete. ANSI has defined various isolation levels. An example is the commonly known “Serializable” isolation level where multiple transactions execute in such a way that the execution schedule is equivalent to a serial schedule where all operations of each transaction are clustered, i.e., transactions appear to have been executed one after another serially. Serializability is the highest degree of isolation.
Independent of the isolation achieved via any locking mechanism, some database operation need that the data records as read by the operation be stable, i.e., the data records the operation visited once never change until the end of the operation execution. This requirement is commonly known as “snapshot” of data. The common language used to execute database operations is the Structured Query Language (SQL). Some SQL statements may need to refer to a tuple, or a set of tuples, satisfying a predicate more than once during their execution. If a Database Management System (DBMS) guarantees that a SQL statement execution will see the same data values each time a given predicate is evaluated, then the DBMS is said to provide “snapshot” isolation.
Prior art describes database systems using two-version techniques, as well as multi-version techniques, that satisfy the above requirements for transactions executing under serializable isolation. However, these schemes have several drawbacks. For example, a read-only transaction must declare itself as such. This is not practical since many DBMSs create SQL statements on the fly and it may not be possible to assess at the start of each and every transaction whether the transaction is read-only or not. Secondly, current analysis and commercial success of a few products demonstrate that though serializable isolation is a theoretically interesting concept, the most practical isolation is the ANSI SQL isolation READ COMMITTED, or variations thereof.
There is currently a need to improve tradeoffs between transaction concurrency and the problems that arise from presently used access control and lock conflict resolution in systems that allow concurrent processing, focusing on efficient implementation for ANSI READ COMMITTED transaction.